package Sequence;

import java.util.*;

public class Test0332 {
    public static void main(String[] args) {
        ArrayList<List<String>> list = new ArrayList<>();
        list.add(List.of("JFK","SFO"));
        list.add(List.of("JFK","ATL"));
        new Solution0332_1().findItinerary(list);
    }
}

class Solution0332_1 {
    LinkedList<String> path;
    public List<String> findItinerary(List<List<String>> tickets) {

        Map<String,Queue<String>> graph = new HashMap<>();

        for (List<String> ticket : tickets) {
            String s1 = ticket.get(0);
            String s2 = ticket.get(1);
            if (!graph.containsKey(s1)) {
                graph.put(s1, new PriorityQueue<>());
            }
            graph.get(s1).add(s2);
        }

        path = new LinkedList<>();

        dfs("JFK",graph);

        return path;

    }


    private void dfs(String start, Map<String,Queue<String>> graph){

        Queue<String> arrivals = graph.get(start);

        while(arrivals != null && !arrivals.isEmpty()){
            dfs(arrivals.poll(),graph);
        }
        path.addFirst(start);
    }
}
